package work;

class Solution {
    public int findPeakElement(int[] nums) {
        // 1 2 3 4 5 6 7 9 10 2 3 4 7
        //二分本质：每次搜索空间减半
        //假设取得中间索引mid，
        //1.mid大于左右两边 mid元素为峰值，返回mid
        //2.左边小于mid，右边大于mid
        //3.左边大于mid，右边小于mid
        //4.左右两边均大于mid
        // 这里引用力扣刷题友的评论：“很多人可能跟我一开始一样，有一个思维误区，就是一次走一半难道不怕错过了一些峰值吗
        // 但是其实这不重要，题目只是要求求出一个峰值，因此只要右边存在答案就可以把左边都抛弃掉，然后只要一直确保这个
        // 区间存在答案，当区间长度为1时，答案就出来了。”
        // 是的，只要确保最终锁定的区间有峰值就行了，不要怕错过其他可能的峰值
        // 比如，当前mid取第2种情况，左边小，右边大，你会想：左边也是有可能有峰值的。这想法没问题，但同时，右边爬坡上去一定会有峰值
        // 我们只需要在乎这一点，然后取mid到right右边界区间。再取mid，如果是第三种情况，那么就可以取左半空间

        int left = 0;
        int right = nums.length-1;
        while (left<right){
            int mid = left + right >> 1;
            int leftNum = Integer.MIN_VALUE;
            int rightNum = Integer.MIN_VALUE;
            if(mid-1>=0){
                leftNum = nums[mid-1];
            }
            if(mid+1<nums.length){
                rightNum = nums[mid+1];
            }
            if(nums[mid]>leftNum&&nums[mid]>rightNum){
                left = mid;
                break;
            } else if (nums[mid]>leftNum&&nums[mid]<rightNum) {
                left = mid + 1;
            } else if (nums[mid]<leftNum&&nums[mid]>rightNum) {
                right = mid -1;
            }else {
                left = mid + 1;
            }
        }

        return left;
    }
}